/* 
 COMP20007 Design of Algorithms 

 Module to supply a graph data structure for Assignment 2.

 Author: Andrew Turpin (aturpin@unimelb.edu.au)
 	 and Jordan Holland 390527
 Date: April 2013

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "vector.h"
#include "vertex.h"
#include "listops.h"
#include "graph.h"

// create an empty graph
Graph *
create_graph() {
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->m = 0;
    g->vertices = vector_new();
    return g;
}

// print graph
void
print_graph(Graph *g) {
    printf("************** GRAPH n=%d m=%d\n",vector_size(g->vertices), g->m);
    for (int i = 0 ; i < vector_size(g->vertices) ; i++) {
        Vertex *v = VERTEX(g, i);
        printf("%3d txt= %s in= %3d out= %3d : ",i, v->text, v->in_degree, v->out_degree);
        Label *j;
        for (j = begin_iterator(v->neighbours) ; j != NULL ; ) {
            printf(LIST_PRINT_FORMAT, *j);
            j = step_iterator(v->neighbours);
        }
        printf("\n");
    }
    fflush(stdout);
}

/*
** Return number of edges in graph
*/
unsigned int get_number_of_edges(Graph *g) { return g->m; }

/*
** Add vertex to graph with text s.
** Does not check for duplicate text!
** Does not make a copy of *s.
** SIDE EFFECTS: may allocate space for vertices vector
*/
Label
add_vertex(Graph *g, char *s) {
    Vertex *v = (Vertex *)malloc(sizeof(Vertex));
    assert(v != NULL);
    v->in_degree  = 0;
    v->out_degree = 0;
    v->text = s;
    v->neighbours = make_empty_list();

    int index = vector_push_back(g->vertices, v);
    assert(index != -1);

    return index;
}

/*
** Add edge(u,v) to graph
** ASSUMES: graph[u] and graph[v] are initialised.
** SIDE EFFECTS: alters graph
*/
void
insert_edge(Graph *g, Label u, Label v) {
    assert((int)u < vector_size(g->vertices));
    assert((int)v < vector_size(g->vertices));
    VERTEX(g,u)->out_degree++;
    VERTEX(g,v)->in_degree++;
    insert_at_foot(VERTEX(g, u)->neighbours, v);
    g->m++;
}

/*
** Find a vertex in path that has out_degree > 0, set it to middle
** Put all vertices before middle in *before 
** and all after middle in *after.
** If there is no vertex with out_degree > 0, set middle to g->n+1 and before and after not defined.
*/
void
split_path(Graph *g, LabelList path, LabelList *before, Label *middle, LabelList *after) {
    Label *i;

    for (i = begin_iterator(path); i != NULL && VERTEX(g, *i)->out_degree == 0; )
        i = step_iterator(path);

    if (i == NULL) {
        *middle = vector_size(g->vertices) + 1;
    } else {
        *middle = *i;
        split_list(path, before, after);
    }
}

/*
** Print strings for each vertex in path
*/
void
print_path(Graph *g, LabelList path) {
    if (list_size(path) < 1)
        return;
    Label *i = begin_iterator(path); 
    int k = strlen(VERTEX(g, *i)->text);
    printf("%s", VERTEX(g, *i)->text);
    i = step_iterator(path);
    while (i != NULL) {
        printf("%c",VERTEX(g, *i)->text[k-1]);
        i = step_iterator(path);
    }
    printf("\n");
}

/**************************
* Students mod below here *
***************************/

// find vertex with out_degree == 0 by cycling through all possible vertices
// if no such vertex, return size of vertices + 1 (g->vertices)
Label
find_end(Graph *g) { 
    int i;
    for (i = 0 ; i < vector_size(g->vertices) ; i++) {
        Vertex *v = VERTEX(g, i);
        if (v->out_degree == 0) {
        	return (Label)i;
        }
    }
    return (Label)vector_size(g->vertices) + 1;
}

// find vertex with in_degree == 0 by cycling through all possible vertices
// if no such vertex, return size of vertices + 1 (g->vertices)
Label
find_start(Graph *g) { 
    int i;
    for (i = 0 ; i < vector_size(g->vertices) ; i++) {
        Vertex *v = VERTEX(g, i);
        if (v->in_degree == 0) {
        	return (Label)i;
        }
    }
    return (Label)vector_size(g->vertices) + 1;
}

/*
** RETURN list of vertices that form a cycle from start.
**        The list includes start at the beginning and at the end
**        If there is no cycle, exits by assert in remove_head function
**	  because there are no more visitable edges (hasn't returned to start)
**	  ASSUMES: - proper input from makeInput.
**	  SIDE EFFECTS:- deletes visited edges in graph and decreases out_degree
**		       - keeps start vertex at end of path as well (need to 
**			 remove in find_euler_path for the initial path)
*/
LabelList
find_cycle(Graph *g, Label start) {
    LabelList path = make_empty_list();
    Vertex *v = VERTEX(g, start);
    insert_at_foot(path, start);
    data_t vertex_label;
    vertex_label = remove_head(v->neighbours);
    
    	//increments through edges till the starting vertex is reached
    while (vertex_label != start) {
    	    v->out_degree--;    	       
    	    v = VERTEX(g, vertex_label);
    	    insert_at_foot(path, vertex_label);
    	    vertex_label = remove_head(v->neighbours); 
    }
    
    v->out_degree--;
    insert_at_foot(path, start);
    
    return path;
}

/*
** RETURN: Exits by assert in find_cycle if no Eulerian path *read above*
**         Otherwise returns a list of vertices that form a Eulerian path
**	   Cycles through path inserting extra paths at points where 
**	   out_degree != 0 till the length of the path is equal to the number
**	   of edges in graph (means complete message).
**	   
*/
LabelList 
find_euler_path(Graph *graph, Label start) {
    LabelList path = find_cycle(graph, start);
    remove_foot(path);		// deletes start vertex from the end of path
    LabelList before, after;
    LabelList euler_path;	// temp path for extra cycles in main path
    Label middle;
    
    while (graph->m > list_size(path)){
    	  split_path(graph, path, &before, &middle, &after);
    	  euler_path = find_cycle(graph, middle);
    	  path = join_lists(before, euler_path);
    	  path = join_lists(path, after); 
    	  free(euler_path);	// free memory for every newly created temp path
    }

    return path;
}

